# 长度最小的子数组：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

# 滑动窗口解题，注意是 大于等于 target
class Solution:
    def minSubArrayLen(self, s: int, nums: list) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        ans = n + 1
        start, end = 0, 0
        total = 0
        while end < n:
            total += nums[end]
            while total >= s:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        
        return 0 if ans == n + 1 else ans


# 前缀和及二分查找：
class Solution:
    def minSubArrayLen(self, s: int, nums: list) -> int:
        """
            前缀和加二分查找解题
        """

        # 定义二分查找函数
        def binarySerch(nums, left, right, target):
            start = left
            # i 位置的和 ，必须减去 i -1 的值， 避免下标为0时， 没有 -1下标，默认值为0
            num = nums[start - 1] if start - 1 >= 0 else 0
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] - num >= target:
                    right = mid
                else:
                    left = mid + 1

            # 直接返回的就是序列和的长度
            return left - start + 1 if nums[left] - num >= target else len(nums) + 1

        sumList = [nums[0]]
        # 计算前缀和
        for i in range(1, len(nums)):
            sumList.append(sumList[-1] + nums[i])

        # 因为nums每一项都是大于0的，所以前缀和数组是升序
        ans = len(sumList) + 1
        target = s
        for i in range(len(sumList)):
            ans = min(binarySerch(sumList, i, len(sumList)-1, target), ans)

        return ans if ans != len(nums) + 1 else 0

# nums = [2,3,1,2,4,3]
nums = [1,2,3,4,5]
target = 15
# nums = [7]
# target = 7

s = Solution()
rst = s.minSubArrayLen(target, nums)
print(rst)
